题目链接：uva 1559 - Nim

题目大意：有n个人，奇数的为一队，偶数的为一对，两队分别从一堆石子个数为S的石子堆中取石子，取到最后一个石子一方则视为失败。给出各个队员每次可取石子的上限值，然后按照顺序操作。

解题思路：dp[i][s]表示第i个选手操作时剩s个石子时为必胜还是必败。因为是取到最后一个石子的为输，所以最后递归结束的条件和不同的略有不同。
还尝试过可以将石子数减1，然后普通处理也是可以。

/******************* * 取到最后一个石子的输 * ****************/ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 30; const int maxs = 1<<14; int N, S, m[maxn]; int dp[maxn][maxs]; void init () { memset(dp, -1, sizeof(dp)); scanf("%d", &S); for (int i = 0; i < 2 * N; i++) scanf("%d", &m[i]); } bool dfs (int d, int s) { if (s <= 0) return 1; if (d >= 2 * N) d -= 2 * N; if (dp[d][s] != -1) return dp[d][s]; dp[d][s] = 0; for (int i = 1; i <= m[d]; i++) { if (dfs(d + 1, s - i)) continue; dp[d][s] = 1; } return dp[d][s]; } int main () { while (scanf("%d", &N) == 1 && N) { init(); printf("%d\n", dfs(0, S) ? 1 : 0); } return 0; }